import java.util.ArrayDeque;
import java.util.Deque;

public class MaxSlidingWindow {
    // leetcode 滑动窗口最大值
    // https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 单调栈，从队列头到队列为的元素是递减的顺序
        // 向单调栈中添加元素的时候，如果队列尾的元素小于当前元素的话，那么就弹出最后队列尾的元素
        // 直到单调栈中有序，这里为什么可以弹出栈尾的元素，因为窗口是向右移动的，如果当前元素大于队列尾
        // 的元素，那么队列尾的元素一定是使用不到的，所以可以直接弹出
        Deque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] ret = new int[n-k+1];
        int index = 0;
        for (int i = 0; i < n; i++) {
            // 判断队列头中的元素是否经过窗口的移动出窗口了
            while (!deque.isEmpty() && deque.peek() < i-k+1) {
                deque.poll();
            }
            // 当插入当前元素的时候，需要维护单调栈的有序性
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offer(i);
            if (i >= k-1) {
                ret[index++] = nums[deque.peek()];
            }
        }
        return ret;
    }
}
